package com.daji.search_and_sort;

import java.util.*;

/**
 * 基于 the-Algorithms 网站的 BucketSort进行改进。
 * https://the-algorithms.com/algorithm/bucket-sort
 * @Creator：大吉
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] arr = new int[10];

        /* generate 10 random numbers from -50 to 49 */
        Random random = new Random();
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = random.nextInt(100) - 50;
        }

        bucketSort(arr);
        System.out.println(Arrays.toString(arr));

        /* check array is sorted or not */
        for (int i = 0, limit = arr.length - 1; i < limit; ++i) {
            assert arr[i] <= arr[i + 1];
        }
    }

    /**
     * BucketSort algorithms implements
     *
     * @param arr the array contains elements
     */
    private static void bucketSort(int[] arr) {
        //计算数组最大值和最小值
        int min=arr[0],max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min){
                min = arr[i];
            }
            if (arr[i] > max){
                max = arr[i];
            }
        }

        /* number of buckets */
        int numberOfBuckets = max - min + 1;

        List<List<Integer>> buckets = new ArrayList<>(numberOfBuckets);

        /* init buckets */
        for (int i = 0; i < numberOfBuckets; ++i) {
            buckets.add(new ArrayList<>());
        }

        /* store elements to buckets */
        for (int value : arr) {
            /*
                TODO hash函数的选择。这点就是桶排序的灵活之处
                还有一种hash函数的选择：int hash = (value - min) / (arr.length);
                还有一种hash函数的选择：int hash = hash(value, min, numberOfBuckets);
                你可以根据数据的特点选择任意一种hash函数，来将数据塞入不同的桶中。
                如果这个映射规则设计成：将待排序集合的每个元素一个数据一个桶（一个萝卜一个坑），那么其实就是计数排序。
                如果这个映射规则设计成：将待排序集合的所有元素设计成只有一个桶，那么该排序方法就是基于比较的线性排序方法
            */
            int hash = (int) ((value - min) / (max - min + 1.0) * arr.length);
            buckets.get(hash).add(value);
        }

        //调用某种线性排序算法对桶内元素进行排序（这里利用直接插入排序算法）
        for (int i = 0; i < buckets.size(); i++) {
            buckets.set(i,insertionSort_LinkedList(buckets.get(i)));
        }

        //将每个桶中元素聚合，得到排好序的数组
        //concat -> concatenate v.使连锁，联结
        /* concatenate buckets to origin array */
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int value : bucket) {
                arr[index++] = value;
            }
        }
    }

    //直接插入排序
    private static List<Integer> insertionSort_LinkedList(List<Integer> list){

        Integer[] array = list.toArray(new Integer[0]);
        Integer temp;
        for (int i = 1; i < array.length; i++) {
            temp = array[i];
            if (temp < array[i-1]){ //该元素比已经排好序元素的最大元素还要小
                //遍历并找到已排序好的数组的合适位置
                int j = 0;
                for (j = 0; j < i; j++){
                    if (array[j] > temp) {    //找到了
                        break;
                    }
                }
                for (int k = i; k > j; k--) { //后移
                    array[k] = array[k-1];
                }
                array[j] = temp;
            }
        }
        return Arrays.asList(array);
    }

}
